package algorithms.tree;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * 从前序和中序序列重建二叉树
 * 
 * 算法思想: 根据前序遍历和中序遍历的特征,前序遍历的第一个是树的根节点,
 * 再结合中序序列,将序列划分为左子树和右子树,对于子树,依然可以继续通过查看前序结果划分左子树和右子树, 这是个递归过程,
 * 直到将子树切分成单个节点,就可以作为父节点的左或者右节点了.
 * 
 * 在递归切分过程中,前序结果作为选择root节点的依据(子节点在广义上也是根节点).
 * 
 * @author syx
 *
 */
public class BinaryTreeRebuild {

	public static BinaryNode<Integer> rebuild(Queue<Integer> inOrderQue, Queue<Integer> preOrderQue) {
		// 从前序结果序列遍历root节点
		BinaryNode<Integer> rootNode = new BinaryNode<>(preOrderQue.poll());
		// 通过根节点划分左右子树
		Queue<Integer> tmpleftInOrder = new ArrayDeque<Integer>(inOrderQue.size());
		Queue<Integer> tmprightInOrder = new ArrayDeque<Integer>(inOrderQue.size());
		splitQue(rootNode, tmpleftInOrder, tmprightInOrder, inOrderQue);
		// debug
		print(inOrderQue, preOrderQue, rootNode, tmpleftInOrder, tmprightInOrder);
		// 子树不是单个节点,就继续切分
		if (tmpleftInOrder.size() > 0) {
			rootNode.setLeft(rebuild(tmpleftInOrder, preOrderQue));
		}
		if (tmprightInOrder.size() > 0) {
			rootNode.setRight(rebuild(tmprightInOrder, preOrderQue));
		}
		return rootNode;

	}

	private static void print(Queue<Integer> inOrder, Queue<Integer> preOrderQue, BinaryNode<Integer> rootNode,
			Queue<Integer> tmpleftInOrder, Queue<Integer> tmprightInOrder) {
		System.out.println("-------");
		System.out.println("inOrder:" + inOrder);
		System.out.println("preOrder:" + preOrderQue);
		System.out.println("node:" + rootNode.getKey());
		System.out.println("tmpleft:" + tmpleftInOrder);
		System.out.println("tmpright：" + tmprightInOrder);
		System.out.println("-------");
	}

	private static void splitQue(BinaryNode<Integer> root, Queue<Integer> tmpleftInOrder,
			Queue<Integer> tmprightInOrder, Queue<Integer> baseOrder) {
		boolean arriveMid = false;
		for (Integer i : baseOrder) {
			if (i == root.getKey()) {
				arriveMid = true;
			} else {
				if (arriveMid) {
					tmprightInOrder.offer(i);
				} else {
					tmpleftInOrder.offer(i);
				}
			}
		}
	}

	public static void main(String[] args) {
		Integer[] pre = { 1, 5, 7, 6, 8, 9 };
		Integer[] in = { 7, 5, 6, 1, 9, 8 };
		Queue<Integer> preOrderque = new ArrayDeque<Integer>(6), inOrderque = new ArrayDeque<Integer>(6);

		preOrderque.addAll(Arrays.asList(pre));
		inOrderque.addAll(Arrays.asList(in));

		BinaryNode<Integer> root = rebuild(inOrderque, preOrderque);

		System.out.println("pre:" + root.preorderTraversing());
		System.out.println("in:" + root.inorderTraversing());
		System.out.println("post:" + root.postorderTraversing());
	}
}
